package com.example.leetcode.分治;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。
 * 你需要给出所有可能的组合的结果。有效的运算符号包含 +,-以及*。
 *
 * 示例1:
 *
 * 输入: "2-1-1"
 * 输出: [0, 2]
 * 解释:
 * ((2-1)-1) = 0
 * (2-(1-1)) = 2
 *
 *
 * @Description TODO
 * @date 2021/6/30 15:29
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_1_241 {
    public static void main(String[] args) {

    }
    /**
     * 分治法：
     * 以 2 * 3 - 4 * 5 为例。可以通过运算符把整个式子分成两部分，两部分再利用递归解决
     *  2 和 3 - 4 * 5 两部分，中间是 * 号相连。
     * 有了两部分的结果，然后再通过中间的符号两两计算加入到最终的结果中即可。
     * 比如第一种情况，2 和 3 - 4 * 5 两部分，中间是 * 号相连。
     * 2 的解就是 [2]，3 - 4 * 5 的解就是 [-5, -17]。
     * 把两部分解通过 * 号计算，最终结果就是 [-10, -34]。
     */
    public static List<Integer> diffWaysToCompute(String expression) {
        if (expression == null || expression.length() <= 0) {
            return new ArrayList<>();
        }

        List<Integer> res = new ArrayList<>();

        char[] chars = expression.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '+' || chars[i] == '-' || chars[i] == '*'){
                // 获取操作符左边表达式的所有的结果
                List<Integer> leftString = diffWaysToCompute(expression.substring(0, i));
                // 获取操作符右边表达式的所有的结果
                List<Integer> rightString = diffWaysToCompute(expression.substring(i + 1));

                // 遍历左边的所有结果
                for (Integer leftNumber : leftString) {
                    // 遍历右边的所有结果
                    for (Integer rightNumber : rightString) {
                        if (chars[i] == '+'){
                            res.add(leftNumber + rightNumber);
                        }else if (chars[i] == '-'){
                            res.add(leftNumber - rightNumber);
                        }else {
                            res.add(leftNumber * rightNumber);
                        }
                    }

                }

            }
        }
        if (res.isEmpty()) {
            res.add(Integer.valueOf(expression));
        }
        return res;
    }



}
